package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

/**
 * 0236.二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 说明:
 * ● 所有节点的值都是唯一的。
 * ● p、q 为不同节点且均存在于给定的二叉树中。
 *
 * 归纳如下三点：
 * 1.  求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
 * 2.  在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
 * 3.  要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
 * @author Liyc
 * @date 2024/1/12 17:18
 **/

public class Solution21 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {// 递归结束条件
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p ,q);

        if (left == null && right == null) {// 若未找到节点 p 或 q
            return null;
        } else if (left != null && right == null) {// 若找到一个节点
            return left;
        } else if (left == null && right != null) {// 若找到一个节点
            return right;
        } else {
            return root;
        }
    }
}
